package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * dp
 * c
 * 44. 通配符匹配
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/9 14:17
 */
public class IsMatch2 {


    public static void main(String[] args) {
        IsMatch2 test = new IsMatch2();

        String[] ss = {"aa", "aa", "cb", "adceb", "acdcb",
                "", "aaa", "aaaaaa", "abcabczzzde"};
        String[] ps = {"a", "*", "?a", "*a*b", "a*c?b",
                "mis*is*p*.", "", "?*", "*abc???de*"};

        boolean[] values = {false, true, false, true, false,
                false, false, true, true};
        for (int i = 0; i < 9; i++) {
            boolean match = test.isMatch(ss[i], ps[i]);
            if (match != values[i]) {
                System.out.println(i + "  " + ss[i] + "  " + ps[i] + "   " + values[i]);
            }
        }
        System.out.println("ok");
    }

    public boolean isMatch(String s, String p) {
        int a = s.length();
        int b = p.length();
        boolean[][] arr = new boolean[a + 1][b + 1];
        char[] ac = s.toCharArray();
        char[] bc = p.toCharArray();
        arr[0][0] = true;
        for (int i = 1; i <= b; i++) {
            if (bc[i - 1] == '*') {
                arr[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (ac[i] == bc[j] || bc[j] == '?') {
                    arr[i + 1][j + 1] = arr[i][j];
                } else if (bc[j] != '*') {
                    arr[i + 1][j + 1] = false;
                } else {
                    arr[i + 1][j + 1] = arr[i][j] || arr[i][j + 1] || arr[i + 1][j];
                }
            }
        }
        return arr[a][b];
    }

}
